#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 1e6 + 5;

int n, m;
int a[N], root[N];
int pos[N];
struct Node {
  int sum;
  int ch[2];
} tr[N * 32];
#define sum(p) tr[p].sum
#define lc(p) tr[p].ch[0]
#define rc(p) tr[p].ch[1]

int newnode(int p) {
  static int tot = 0;
  ++tot;
  sum(tot) = sum(p);
  lc(tot) = lc(p);
  rc(tot) = rc(p);
  return tot;
}
void update(int x, int d, int& p, int l, int r) {
  p = newnode(p);
  sum(p) += d;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(x, d, lc(p), l, mid);
  else
    update(x, d, rc(p), mid + 1, r);
}
void build() {
  rep(i, 1, n) {
    int x = a[i];
    int pre = pos[x];
    pos[x] = i;
    root[i] = root[i - 1];
    if (pre) update(pre, -1, root[i], 1, n);
    update(i, 1, root[i], 1, n);
  }
}
int query(int L, int R, int p, int l, int r) {
  if (L <= l && R >= r) return sum(p);
  int mid = (l + r) >> 1;
  int res = 0;
  if (L <= mid) res += query(L, R, lc(p), l, mid);
  if (R > mid) res += query(L, R, rc(p), mid + 1, r);
  return res;
}

int read() {
  int s = 0;
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
  return s;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  n = read();
  rep(i, 1, n) a[i] = read();
  build();
  m = read();
  while (m--) {
    int l, r;
    l = read(), r = read();
    cout << query(l, r, root[r], 1, n) << endl;
  }
  return 0;
}